These pages are obsolete

Table (d’entiers)

table.h

Dans un fichier table.h, créer un type structuré Table avec trois champs :

• le pointeur vers le tableau en mémoire, “data”
• la taille du tableau en mémoire, “size”
• le nombre d’éléments dans la table, “n”

Ajouter une constante RATIO égale à 50.

Déclarer les fonctions suivantes :

• Table* new_table(int size); alloue dynamiquement une nouvelle table, initialise correctement tous les champs et renvoie son adresse ou NULL en cas de problème d’allocation ;
• void free_table(Table*); libère la mémoire associée à une table allouée dynamiquement ;
• void print_table(Table*); affiche les n éléments d’une table, encadrés par des [] et séparés par des , (la table est passée par adresse uniquement pour économiser une copie) ;
• int is_sorted(Table*); renvoie 1 si les éléments de la table sont triés par ordre croissant, 0 sinon ;
• int dicho_search(Table* t,int x); réalise une recherche dichotomique de l’élément x dans une table triée et renvoie sa position, ou -1 si l’élément n’est pas dans la table (vous pourrez utiliser pour écrire cette fonction une fonction intermédiaire dicho_rec() qui prend plus de paramètres, mais elle ne doit pas apparaitre dans le .h) ;
• int insert(Table * t, int e); ajoute e dans une table triée, avec réallocation de la mémoire associée à la table si nécessaire (on choisira alors une nouvelle taille pour que le taux d’occupation soit égal à RATIO), renvoie la position de l’élément ajouté ou -1 si l’ajout n’a pas été possible (erreur d’allocation mémoire) ;
• int random_inserts(Table* t, int nb); réalise l’ajout de nb valeur aléatoire dans la table, renvoie le nombre d’ajouts effectués ;
• void shuffle(Table* t); mélange le tableau aléatoirement ;

procédure shuffle(tableau T)
  pour i de 0 à taille(T)-1
    # tirer un nombre aléatoire entre 0 et taille(T)
        r ← random(0,taille(T))
        # échanger les valeurs aux positions i et r
        swap(T[i], T[r])

procédure shuffle(tableau T)
  pour i de 0 à taille(T)-1
    # tirer un nombre aléatoire entre 0 et taille(T)
        r ← random(0,taille(T))
        # échanger les valeurs aux positions i et r
        swap(T[i], T[r])

• int del(Table * t, int e); enlève e dans une table triée, avec réallocation de la mémoire associée à la table si l’occupation de la table est inférieur à RATIO pourcent (la nouvelle taille devra être l’ancienne divisée par deux si possible, sinon égale exactement au nombre d’éléments), renvoie l’ancienne position de l’élément e ou -1 si deletion impossible (élément non présent) ;
• BONUS int del_mutiple(Table * t, int e); enlève toutes les occurances de e dans d’une table, renvoie le nombre de délétions effectuées ;
• BONUS int clean(Table * t); enlève tous les doublons dans une table, renvoie le nombre de délétions effectuées ;
• void insertion_sort(Table* t); réalise le tri par insertion de la table t ;

procédure tri_insertion(tableau T)
  pour i de 1 à taille(T) - 1
    # mémoriser T[i] dans x
    x ← T[i]                            
    # décaler les éléments T[0]..T[i-1] qui sont plus grands que x, en partant de T[i-1]
    j ← i                               
    tant que j > 0 et T[j - 1] > x
      T[j] ← T[j - 1]
      j ← j - 1
    # placer x dans le "trou" laissé par le décalage
    T[j] ← x   

procédure tri_insertion(tableau T)
  pour i de 1 à taille(T) - 1
    # mémoriser T[i] dans x
    x ← T[i]                            
    # décaler les éléments T[0]..T[i-1] qui sont plus grands que x, en partant de T[i-1]
    j ← i                               
    tant que j > 0 et T[j - 1] > x
      T[j] ← T[j - 1]
      j ← j - 1
    # placer x dans le "trou" laissé par le décalage
    T[j] ← x   

• void quick_sort(Table* t, int(*pivot)(Table*,int,int)); réalise le tri quicksort en prenant comme fonction de choix de pivot la fonction passée en paramètre ;

partitionner(tableau T, entier premier, entier dernier, entier pivot)
  échanger T[pivot] et T[premier]  # échange le pivot avec le premier du tableau , le pivot devient le premier du tableau
  pivot ← premier
  Tant que premier < dernier
    Tant que T[premier] <= T[pivot] ET premier < Taille(T)
        premier ← premier + 1
    Tant que T[dernier] >= T[pivot] ET dernier > pivot
      dernier ← dernier - 1
    si premier < dernier alors
      échanger T[premier] et T[dernier]
  échanger T[dernier] et T[pivot]
  renvoyer dernier

tri_rapide(tableau T, entier premier, entier dernier)
        si premier < dernier alors
            pivot ← choix_pivot(T, premier, dernier)
            pivot ← partitionner(T, premier, dernier, pivot)
            tri_rapide(T, premier, pivot-1)
            tri_rapide(T, pivot+1, dernier)

partitionner(tableau T, entier premier, entier dernier, entier pivot)
  échanger T[pivot] et T[premier]  # échange le pivot avec le premier du tableau , le pivot devient le premier du tableau
  pivot ← premier
  Tant que premier < dernier
    Tant que T[premier] <= T[pivot] ET premier < Taille(T)
        premier ← premier + 1
    Tant que T[dernier] >= T[pivot] ET dernier > pivot
      dernier ← dernier - 1
    si premier < dernier alors
      échanger T[premier] et T[dernier]
  échanger T[dernier] et T[pivot]
  renvoyer dernier

tri_rapide(tableau T, entier premier, entier dernier)
        si premier < dernier alors
            pivot ← choix_pivot(T, premier, dernier)
            pivot ← partitionner(T, premier, dernier, pivot)
            tri_rapide(T, premier, pivot-1)
            tri_rapide(T, pivot+1, dernier)

• int pivot_first(Table*, int b, int e); renvoit b ;
• int pivot_middle(Table*, int b, int e); renvoit l’indice du milieu du sous tableau considéré, c’est à dire (e-b)/2+b;
• int pivot_random(Table*, int b, int e); renvoit un entier aléatoire entre b et e:w.

table.c et test.c

Dans un fichier table.c, écrivez le code des fonctions et dans un fichier test.c écrivez une fonction main() permettant de tester.
Vous compilerez à l’aide de l’utilitaire make (il faut donc écrire un fichier Makefile).

Comptage

Ajoutez une constante DEBUG et du code dans chacune de vos fonctions : si DEBUG vaut 1, vos fonctions comptent le nombre d’opérations effectués et l’affiche avant de terminer. Sinon rien ne change.

Comparez les valeurs en faisant varier la taille de votre table.